package com.heima.leetcode.practice;

import java.util.LinkedList;

/**leetcode 222. 完全二叉树的节点个数
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/3 9:47
 */
public class E222 {

    /**
     * <h3>方法一：拆分分别计算，效率最高</h3>
     * @param root 完全二叉树的根节点
     * @return 节点个数
     */
    public int countNodes1(TreeNode root) {
        if (root == null) {
            return 0;
        }
        TreeNode curr = root;
        // 1. 统计所有层的高度
        int height = 0;
        while (curr != null) {
            curr = curr.left;
            height++;
        }
        // 2. 计算满层的节点个数
        int count = power(height - 1) - 1;
        // 3. 计算最后一层的节点个数
        int maxLength = power(height - 1);
        int index = 0; // 初始是0，记录的是当前节点的索引
        while (index < maxLength) {
            if (exists(root, height, index)) {
                index++; // 当前索引处的节点存在后index才会++，所以循环结束后的index 就是最后一层的节点个数
            } else {
                break;
            }
        }
        return count + index;
    }

    /**
     * 完全二叉树的第height层，index索引的节点是否存在，height从1计数，index从0计数
     * @param root 完全二叉树的根节点
     * @param height 高度，从1开始计数
     * @param index 索引，从0开始计数
     * @return  存在返回true，不存在返回false
     */
    private boolean exists(TreeNode root, int height, int index) {
        int left = 0; // 最后一层的索引开始
        int right = power(height - 1) - 1; // 最后一层的索引结束（索引最大值）
        TreeNode curr = root;
        for (int i = 0; i < height - 1; i++) { // 对前面 height - 1 层进行二分查找，进行这么多次，curr就到最后一层了
            int median = (left + right) >>> 1;
            if(index < median){
                curr = curr.left;
                right = median - 1;
            } else if(median < index){
                curr = curr.right;
                left = median + 1;
            } else{
                curr = curr.left; // index == median，说明要找的节点的索引就在这条线的平行上，让curr = curr.left继续沿着这条线走一步
                right = median; // 缩小范围
            }
        }
        return curr != null;
    }

    /**
     * 2的height次方
     * @param height 高度
     * @return 计算结果
     */
    private int power(int height) {
        return 1 << height;
    }

    /**
     * <h3>方法二：递归的深度优先遍历（preorder），效率和方法一相当</h3>
     * @param root 完全二叉树的根节点
     * @return 节点个数
     */
    public int countNodes2(TreeNode root) {
        if (root == null){
            return 0;
        }
        return 1 + countNodes2(root.left) + countNodes2(root.right);
    }

    /**
     * <h3>方法三：非递归深度优先遍历，写的思路是后序遍历</h3>
     * @param root 完全二叉树的根节点
     * @return 节点个数
     */
    public int countNodes3(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode curr = root;
        TreeNode lastPop = null;
        int count = 0;
        while (curr != null || !stack.isEmpty()){
            if (curr != null){
                stack.push(curr);
                count++; // 用先序遍历统计
                curr = curr.left;
            }else {
                TreeNode last = stack.peek();
                if (last.right == null){
                    // count++; // 用中续遍历统计
                    lastPop = stack.pop();
                    // count++; // 用后续遍历统计
                } else if (last.right == lastPop) {
                    lastPop = stack.pop();
                    // count++; // 用后序遍历统计
                } else {
                    // count++; // 用中序遍历统计
                    curr = last.right;
                }
            }
        }
        return count;
    }

    /**
     * <h3>方法四：层序遍历</h3>
     * @param root 完全二叉树的根节点
     * @return 节点个数
     */
    @SuppressWarnings("all")
    public int countNodes4(TreeNode root) {
        if (root == null){
            return 0;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int count = 1;
        while (!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode poll = queue.poll();
                if (poll.left != null){
                    queue.add(poll.left);
                    count++;
                }
                if (poll.right != null){
                    queue.add(poll.right);
                    count++;
                }
            }
        }
        return count;
    }
}
